import collections
from typing import List
class Solution:
    # 排序
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)
        for st in strs:
            keys = "".join(sorted(st))
            mp[keys].append(st)
        return list(mp.values())
    '''
    复杂度分析
    时间复杂度：O(nklogk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。
    需要遍历 n 个字符串，对于每个字符串，需要 O(klogk) 的时间进行排序以及 O(1) 的时间更新哈希表，
    因此总时间复杂度是 O(nklogk)。
    空间复杂度：O(nk)，其中 n 是 strs 中的字符串的数量，k 是 strs 
    中的字符串的的最大长度。需要用哈希表存储全部字符串。
    '''

    # 计数
    def groupAnagrams2(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)
        for st in strs:
            counts = [0] * 26
            for ch in st:
                counts[ord(ch) - ord("a")] += 1
            # 需要将list转换成tuple才能进行哈希
            mp[tuple(counts)].append(st)
        return list(mp.values())
    '''
    复杂度分析
    时间复杂度：O(nklogk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。
    需要遍历 n 个字符串，对于每个字符串，需要 O(klogk) 的时间进行排序以及 O(1) 的时间更新哈希表，
    因此总时间复杂度是 O(nklogk)。
    空间复杂度：O(nk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。
    '''


strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

# mp = collections.defaultdict(list)
# print(mp)
# for st in strs:
#     keys = "".join(sorted(st))
#     mp[keys].append(st)
# print(mp.values())
mp = collections.defaultdict(list)
print(mp)
for st in strs:
    counts = [0]*26
    print("st=",counts)
    for ch in st:
        counts[ord(ch) - ord("a")] += 1
    print(tuple(counts))
    mp[tuple(counts)].append(st)
    print(mp,list(mp.values()))